package com.test.map;

import java.util.Objects;

import net.sf.json.JSONObject;

public class MHashMap<K, V> {
	transient MHashMap.Entry<K, V>[] table ;
	static final int DEFAULT_CAPACITY = 1 << 4;
	static final float DEFAULT_LOADFACTOR = 0.75f;
	transient int size = 0;
	int capacity = 0;
	float loadFactor = 0;
	int modCount = 0;
	static final int MAX_CAPACITY = Integer.MAX_VALUE;
	static final Entry<?, ?>[] EMPTY_TABLE = {};

	public MHashMap(int capacity, float loadFactor) throws Exception{
		if(capacity <= 0){
			throw new Exception("error capacity");
		}
		if(capacity > MAX_CAPACITY){
			capacity = MAX_CAPACITY;
		}
		if(loadFactor <= 0 || loadFactor >= 1){
			throw new Exception("error loadFactor");
		}
		this.loadFactor = loadFactor;
		this.capacity = capacity;
		init();
	}
	
	public MHashMap(int capacity) throws Exception{
		this(capacity, DEFAULT_LOADFACTOR);
	}
	
	public MHashMap() throws Exception{
		this(DEFAULT_CAPACITY, DEFAULT_LOADFACTOR);
	}
	
	public void init(){
		this.table = new Entry[this.capacity];
	}
	
	public V put(K key, V value){
		if(key == null){
			return putForNullKey(value);
		}
		int hash = hash(key.hashCode());
		int bucketIndex = indexFor(hash);
		for(Entry<K, V> e = table[bucketIndex]; e != null; e = e.next){
			if(e.hash == hash && (e.key == key || e.key.equals(key))){
				V oldValue = e.getValue();
				e.value = value;
				return oldValue;
			}
		}
		modCount++;
		addEntry(hash, key, value, bucketIndex);
		return null;
	}
	
	private void addEntry(int hash, K key, V value, int bucketIndex){
		Entry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new Entry<K, V>(key, value, hash, e);
		if(size++ >= this.capacity * this.loadFactor){
			resize(2 * this.capacity);
		}
	}
	
	private V putForNullKey(V value){
		for(Entry<K, V> e = table[0]; e != null; e = e.next){
			if(e.key == null){
				V oldValue = e.getValue();
				e.value = value;
				return oldValue;
			}
		}
		modCount++;
		addEntry(0, null, value, 0);
		return null;
	}
	
	private V getForNullKey(){
		for(Entry<K, V> e = table[0]; e != null; e = e.next){
			if(e.key == null){
				return e.value;
			}
		}
		return null;
	}
	
	private void resize(int capacity){
		Entry<K, V>[] oldTable = table;
		int oldCapacity = oldTable.length;
		if(oldCapacity == MAX_CAPACITY){
			capacity = Integer.MAX_VALUE;
		}
		Entry<K, V>[] newTable = new Entry[capacity];
		transfer(newTable);
		table = newTable;
	}
	
	private void transfer(Entry[] newTable){
		Entry[] src = table;
		int newCapacity = newTable.length;
		this.capacity = newCapacity;
		for(int j=0; j<src.length; j++){
			Entry<K, V> e = src[j];
			if(e != null){
				src[j] = null;
				do{
					Entry<K, V> next = e.next;
					int i= indexFor(e.hash);
					e.next = newTable[i];
					newTable[i] = e;
					e = next;
				}while(e != null);
			}
		}
	}
	
	public V get(Object key){
		if(key == null){
			return getForNullKey();
		}
		int hash = hash(key.hashCode());
		int bucketIndex = indexFor(hash);
		for(Entry<K, V> e = table[bucketIndex]; e != null; e = e.next){
			if(e.hash == hash && (e.key == key || e.key.equals(key))){
				return e.value;
			}
		}
		return null;
	}
	
	private int hash(int h){
		h ^= (h >>> 20) ^ (h >>> 12);
	    return h ^ (h >>> 7) ^ (h >>> 4);
	}
	
	private int indexFor(int hashCode){
		return hashCode & (this.capacity - 1);
	}
	private static class Entry<K, V> {
		final K key;
		V value;
		Entry<K, V> next;
		int hash;

		public Entry(K k, V v, int h, Entry<K, V> n) {
			key = k;
			value = v;
			next = n;
			hash = h;
		}

		public final V getValue() {
			return value;
		}

		public final void setValue(V value) {
			this.value = value;
		}

		public final K getKey() {
			return key;
		}
		
		public final boolean equals(Object o){
			if(o == null || !(o instanceof MHashMap.Entry)){
				return false;
			}
			MHashMap.Entry<K, V> entry = (MHashMap.Entry<K, V>) o;
			if(this == o){
				return true;
			}
			if(key == entry.getKey() || (key != null && key.equals(entry.getKey()))){
				if(value == entry.getValue() || (value != null && value.equals(entry.getValue()))){
					return true;
				}
			}
			return false;
		}
		
		public final int hashCode(){
			return Objects.hashCode(this.getKey()) ^ Objects.hashCode(this.getValue());
		}
		
		public final String toString(){
			return this.key + "=" + this.value;
		}
	}

	public static void main(String[] args) throws Exception {
		MHashMap m = new MHashMap();
		m.put("1", "aa");
		m.put(null, "bb");
		System.out.println(JSONObject.fromObject(m));
	}
}
